package com.charith;

import java.util.Arrays;
import java.util.Random;

public class BinarySearch {

	public static int binarySearch(int[] array, int target) {
		int low = 0;
		int high = array.length - 1;
		while (low <= high) {
			int mid = calculateMidPoint(low, high);
			int midValue = array[mid];

			if (midValue < target)
				low = mid + 1;
			else if (midValue > target)
				high = mid - 1;
			else {
				while (mid != 0 && target == array[mid - 1])
					// loop backward to check whether duplicate values present
					mid -= 1;
				return mid;
			}
		}
		return -1;
	}

	public static int binarySearchComparisonCount(int[] array, int target) {
		int low = 0;
		int high = array.length - 1;
		int counter = 0;
		while (low <= high) {
			counter++;
			int mid = calculateMidPoint(low, high);
			int midValue = array[mid];

			if (midValue < target)
				low = mid + 1;
			else if (midValue > target)
				high = mid - 1;
			else {
				return counter;
			}
		}
		return counter;
	}

	static int calculateMidPoint(int low, int high) {
		return (low + high) >>> 1;
	}

	public static int[] randomSortedArray(int maxArraySize, int maxValue) {
		Random random = new Random();
		int arraySize = 1 + random.nextInt(maxArraySize);
		int[] array = new int[arraySize];
		for (int i = 0; i < arraySize; i++) {
			array[i] = random.nextInt(maxValue);
		}
		Arrays.sort(array);
		return array;
	}

}
